package com.leetcode.demo;

/**
 * @Author: WuPeng
 * @Date: 2021/6/25 10:42 上午
 */
public class StrStr {

    private int[] getNext(String needle){
        int[] next = new int[needle.length()];
        int j=-1;
        next[0] = j;
        for (int i = 1; i < needle.length(); i++) {
            while (j>=0 && needle.charAt(i) != needle.charAt(j+1))
                j = next[j];
            if (needle.charAt(i) == needle.charAt(j+1))
                j++;
            next[i] = j;
        }
        return next;
    }

    public int strStr(String hayStack, String needle){

        if (needle.length() == 0) return 0;
        int[] next = getNext(needle);
        int j = -1;
        for (int i = 0; i < hayStack.length(); i++) {
            while (j>=0 && hayStack.charAt(i) != needle.charAt(j+1))
                j=next[j];
            if (hayStack.charAt(i) == needle.charAt(j+1))
                j++;
            if (j == needle.length()-1)
                return i-needle.length()+1;

        }
        return -1;
    }

    public static void main(String[] args) {
        StrStr strStr = new StrStr();
        int i = strStr.strStr("aabaabaaf", "aabaaf");
        System.out.println(i);
    }


}
